package com.origin.niuke.linkedlist;

import general_class.ListNode;

/**
 * 两两交换链表的节点
 * 算法：递归
 *
 * @author yezh
 * @date 2023/2/1 22:10
 */
public class NC186 {

    public ListNode swapLinkedPair_recursion(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = head.next, tail = head.next.next;
        head.next.next = head;
        head.next = swapLinkedPair_recursion(tail);
        return newHead;
    }

    public ListNode swapLinkedPair(ListNode head) {
        // write code here
        if (head == null) return null;
        ListNode ans = new ListNode(-1), cur = ans;
        ans.next = head;
        while (cur.next != null && cur.next.next != null) {
            ListNode next1 = cur.next, next2 = cur.next.next, next3 = cur.next.next.next;
            cur.next.next.next = next1;
            cur.next.next = next3;
            cur.next = next2;
            cur = next1;
        }
        return ans.next;
    }

}
